package linkedlist;

import org.junit.Test;

import static linkedlist.ListNode.buildList;
import static linkedlist.ListNode.printList;

public class OddEvenLinkedList328 {
    @Test
    public void test() {
        print(buildList(1));
        print(buildList(1, 2));
        print(buildList(1, 2, 3));
        print(buildList(1, 2, 3, 4));
    }

    public void print(ListNode list) {
        printList(list, "origin");
        list = oddEvenList(list);
        printList(list, "oddEven");
        System.out.println();
    }

    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode oddTail = head;
        ListNode evenHead = head.next;
        ListNode evenTail = evenHead;

        // 1. -> [2] -> 3 -> 4 -> 5 -> 6 -> null
        // 1 -> 3. -> [2 -> 4] -> 5 -> 6 -> null
        // 1 -> 3 -> 5. -> [2 -> 4 -> 6]-> null
        while (evenTail != null && evenTail.next != null) {
            ListNode odd = evenTail.next;

            oddTail.next = odd;
            evenTail.next = odd.next;
            odd.next = evenHead;

            oddTail = oddTail.next;
            evenTail = evenTail.next;
        }
        return head;
    }
}
